\documentclass{beamer}
\usepackage[latin1]{inputenc}
\beamertemplateshadingbackground{red!10}{blue!10}
%\usepackage{fancybox}
\usepackage{epsfig}
\usepackage{verbatim}
\usepackage{url}
%\usepackage{graphics}
%\usepackage{xcolor}
\usepackage{fancybox}
\usepackage{moreverb}
%\usepackage[all]{xy}
\usepackage{listings}
\usepackage{filecontents}
\usepackage{graphicx}

\lstset{
  language=Lisp,
  basicstyle=\scriptsize\ttfamily,
  keywordstyle={},
  commentstyle={},
  stringstyle={}}

\def\inputfig#1{\input #1}
\def\inputeps#1{\includegraphics{#1}}
\def\inputtex#1{\input #1}

\inputtex{logos.tex}

%\definecolor{ORANGE}{named}{Orange}

\definecolor{GREEN}{rgb}{0,0.8,0}
\definecolor{YELLOW}{rgb}{1,1,0}
\definecolor{ORANGE}{rgb}{1,0.647,0}
\definecolor{PURPLE}{rgb}{0.627,0.126,0.941}
\definecolor{PURPLE}{named}{purple}
\definecolor{PINK}{rgb}{1,0.412,0.706}
\definecolor{WHEAT}{rgb}{1,0.8,0.6}
\definecolor{BLUE}{rgb}{0,0,1}
\definecolor{GRAY}{named}{gray}
\definecolor{CYAN}{named}{cyan}

\newcommand{\orchid}[1]{\textcolor{Orchid}{#1}}
\newcommand{\defun}[1]{\orchid{#1}}

\newcommand{\BROWN}[1]{\textcolor{BROWN}{#1}}
\newcommand{\RED}[1]{\textcolor{red}{#1}}
\newcommand{\YELLOW}[1]{\textcolor{YELLOW}{#1}}
\newcommand{\PINK}[1]{\textcolor{PINK}{#1}}
\newcommand{\WHEAT}[1]{\textcolor{wheat}{#1}}
\newcommand{\GREEN}[1]{\textcolor{GREEN}{#1}}
\newcommand{\PURPLE}[1]{\textcolor{PURPLE}{#1}}
\newcommand{\BLACK}[1]{\textcolor{black}{#1}}
\newcommand{\WHITE}[1]{\textcolor{WHITE}{#1}}
\newcommand{\MAGENTA}[1]{\textcolor{MAGENTA}{#1}}
\newcommand{\ORANGE}[1]{\textcolor{ORANGE}{#1}}
\newcommand{\BLUE}[1]{\textcolor{BLUE}{#1}}
\newcommand{\GRAY}[1]{\textcolor{gray}{#1}}
\newcommand{\CYAN}[1]{\textcolor{cyan }{#1}}

\newcommand{\reference}[2]{\textcolor{PINK}{[#1~#2]}}
%\newcommand{\vect}[1]{\stackrel{\rightarrow}{#1}}

% Use some nice templates
\beamertemplatetransparentcovereddynamic

\newcommand{\A}{{\mathbb A}}
\newcommand{\degr}{\mathrm{deg}}

\title{First-class global environments for \commonlisp{}}

\author{Robert Strandh}
\institute{
LaBRI, University of Bordeaux
}
\date{April, 2015}

%\inputtex{macros.tex}


\begin{document}
\frame{
\resizebox{3cm}{!}{\includegraphics{Logobx.pdf}}
\hfill
\resizebox{1.5cm}{!}{\includegraphics{labri-logo.pdf}}
\titlepage
\vfill
\small{European Lisp Symposium, London, UK \hfill ELS2015}
}

\setbeamertemplate{footline}{
\vspace{-1em}
\hspace*{1ex}{~} \GRAY{\insertframenumber/\inserttotalframenumber}
}

\frame{
\frametitle{Context: The \sicl{} project}

https://github.com/robert-strandh/SICL

Several objectives:

\begin{itemize}
\item Create high-quality \emph{modules} for implementors of
  \commonlisp{} systems.
\item Improve existing techniques with respect to algorithms and data
  structures where possible.
\item Improve readability and maintainability of code.
\item Improve documentation.
\item Ultimately, create a new implementation based on these modules.
\end{itemize}
}

\frame{
\frametitle{Environments in the \hs{}}

Mostly used to distinguish the \emph{global environment} from a
\emph{local} (lexical) environment.
\vskip 0.25cm
For example, \texttt{setf} might need to call \texttt{macroexpand}
with the same environment, in case it is wrapped in \texttt{macrolet}
or \texttt{symbol-macrolet}.
}

\frame{
\frametitle{Global environments in the \hs{}}

Occasionally, used to distinguish between the compile-time
\emph{evaluation environment} and the global run-time environment.
\vskip 0.25cm
Example from \texttt{find-class}:
\begin{quotation}
  The \emph{environment} might be used to distinguish between a
  compile-time and a run-time environment.
\end{quotation}
\vskip 0.25cm
Other examples: \texttt{typep}, \texttt{subtypep}, \texttt{constantp},
and \texttt{compiler-macro-function}.
\vskip 0.25cm
However, the \hs{} explicitly allows for all global environments to be
one and the same.

}

\frame{
\frametitle{Global environments in typical implementations}

A typical implementation has a single global environment as allowed by
the \hs{}.  It is typically \emph{spread out} in that a \emph{symbol}
might contain a \emph{function cell} and/or a \emph{value cell}.
\vskip 0.25cm
Some implementations store the function named \emph{foo} in a slot of
the symbol named \emph{foo} but they store the function named
\texttt{(setf \textsf{\emph{foo}})} elsewhere.
\vskip 0.25cm
This discrepancy might reflect the fact that the basic implementation
pre-dates the introduction of \texttt{setf} functions.

}

\frame{
\frametitle{Previous work}

\begin{itemize}
\item Gelernter, Jagannathan, and London (1987) defined first-class
  environments to replace a variety of constructs, including modules
  and classes.
\item Miller and Rozas (1991) used first-class environments as a basis
  for an object system.  No performance penalty if not used.
\item Queinnec and Rourke (1996) defined first-class environments for
  modules for extensive code sharing.  No serious performance penalty.
\item Ron Garret propose using first-class environments to replace
  packages.
\end{itemize}

In all cases, it is a user-visible feature.

}

\frame{
\frametitle{First-class global environments}

In \sicl{}, we put all environment-related information in an
\texttt{environment} class instance.  This environment would typically
be organized as a collection of hash tables, one for each
\emph{namespace}:
\begin{itemize}
\item The \emph{function} namespace, containing information about
  functions, macros, and special operators.
\item The \emph{variable} namespace, containing information about
  special variables, constant variables, and symbol macros.
\item The \emph{type} namespace, containing types defined by
  \texttt{deftype}.
\item The \emph{class} namespace, containing a mapping from class
  names (symbols) to class metaobjects.
\item The \emph{package} namespace, containing mappings from package
  names (strings) to package objects.
\item etc.
\end{itemize}
}

\frame[containsverbatim]{
\frametitle{A protocol for first-class global environments}

However, the current paper is only about a \clos{}-based
\emph{protocol} for first-class global environments.
\vskip 0.25cm
Most protocol functions are generic versions of existing functions:

\begin{verbatim}
(cl:in-package #:sicl-genv)

(defgeneric fboundp (function-name environment))

(defgeneric fmakunbound (function-name environment))
\end{verbatim}

}

\frame[containsverbatim]{
\frametitle{A protocol for first-class global environments}

Some functions are new, but needed to implement some standard
\commonlisp{} functionality

\begin{verbatim}
(cl:in-package #:sicl-genv)

(defgeneric type-expander (symbol environment))

(defgeneric (setf type-expander) (new symbol environment))
\end{verbatim}

}

\frame[containsverbatim]{
\frametitle{Example: implementing \texttt{cl:fboundp}}

\begin{verbatim}
(defun fboundp (name)
  (sicl-genv:fboundp
    name
    (load-time-value (sicl-genv:global-environment))))
\end{verbatim}

The package named \texttt{sicl-genv} is the one containing the
protocol definitions.
\vskip 0.25cm
The function \texttt{sicl-genv:global-environment} returns the current
global environment.

}

\frame{
\frametitle{Performance issue}

We must make sure that typical run-time uses of the environment do not
penalize performance, in particular for:

\begin{itemize}
\item Accessing a globally defined function in order to call it.
\item Accessing the global value of a special variable.
\end{itemize}

We must use an \emph{indirection} to allow functions to be redefined,
and values of variables to be modified.
\vskip 0.25cm
For that, the environment contains a \emph{cell} for each function and
each variable.

}

\frame[containsverbatim]{
\frametitle{Reference to a global function}

The compiler turns a reference to a global function \texttt{foo} into
something like:

\begin{verbatim}
(car
  (load-time-value
    (sicl-genv:function-cell
      'foo
      (sicl-genv:global-environment+))))
\end{verbatim}

Here \texttt{car} is not really the standard \commonlisp{} function,
because the argument is known to be a \texttt{cons} cell.

}

\frame[containsverbatim]{
\frametitle{Other performance issues}

Our environment incurs a performance penalty when the name of a
function or a variable is known only at run-time:

\begin{verbatim}
(fdefinition x)
(symbol-value x)
\end{verbatim}

But when the name is known at compile time:

\begin{verbatim}
(fdefinition 'my-function)
(symbol-value 'my-variable)
\end{verbatim}

we can use a compiler macro.

}


\frame[containsverbatim]{
  \frametitle{Main reason for first-class global environments}

We needed first-class global environments for bootstrapping.
\vskip 0.25cm
The \sicl{} cross compiler works against a first-class global
environment.
\vskip 0.25cm
We can then read and compile code for standard \commonlisp{} functions
using normal package names:

\begin{verbatim}
(defpackage #:sicl-cons
  (:use #:common-lisp))
...
(cl:in-package #:sicl-cons)

(defun cadr (object)
  (car (cdr object)))
\end{verbatim}
}

\frame{
  \frametitle{Other uses for first-class global environments}

  \begin{itemize}
  \item Distinguish between compile-time and run-time global
    environment.
  \item Hide dangerous functions that could compromise the integrity
    of the system.
  \item Sandboxing.
  \item Dealing with multiple versions of packages.
  \item Separate global environment for large applications.
  \end{itemize}
}

\frame{
\frametitle{Future work}

\begin{itemize}
\item Extend protocol to include environment \emph{inheritance}.
\item Design technique for efficient environment cloning.
\item Create a multi-user system based on first-class global
  environments.
\end{itemize}

}

\frame{
  \frametitle{Acknowledgments}

We would like to thank Alastair Bridgewater, David Murray, Robert
Smith, Nicolas Hafner, and Bart Botta for providing valuable feedback
on early versions of this paper.
}

\frame{
\frametitle{Thank you}

Questions?
}

%% \frame{\tableofcontents}
%% \bibliography{references}
%% \bibliographystyle{alpha}

\end{document}
